package LeetCode.exercise;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class LCR159 {
    public static void main4(String[] args) {
        LCR159 l = new LCR159();
        System.out.println(Arrays.toString(l.inventoryManagement(new int[]{2, 5, 7, 4}, 1)));
    }

    public int[] inventoryManagement(int[] stock, int cnt) {
        inventory(stock, 0, stock.length - 1, cnt);
        int[] res = new int[cnt];
        for (int i = 0; i < res.length; i++) {
            res[i] = stock[i];
        }
        return res;
    }

    public void inventory(int[] arr, int start, int end, int cnt) {
        int target = arr[new Random().nextInt(end - start + 1) + start];
        int left = start - 1, i = start, right = end + 1;
        while (i < right) {
            if (target > arr[i]) {
                swap(arr, ++left, i++);
            } else if (target == arr[i]) {
                i++;
            } else {
                swap(arr, --right, i);
            }
        }
        int a = left - start + 1, c = end - right + 1, b = (right - 1) - (left + 1) + 1;
        if (cnt < a) {
            inventory(arr, start, left, cnt);
        } else if (cnt <= a + b) {
            return;
        } else {
            inventory(arr, right, end, cnt - a - b);
        }
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            in.nextLine();
            String str1 = in.next();
            String str2 = in.next();
            in.nextLine();
            String[] arr = new String[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.next();
            }
            int i = 0, j = -1, res = Integer.MAX_VALUE;
            while (i < n) {
                if (arr[i].equals(str1) || arr[i].equals(str2)) {
                    if (j >= 0 && !arr[j].equals(arr[i])) {
                        res = Math.min(res, i - j);
                    }
                    j = i;
                }
                i++;
            }
            if (res == Integer.MAX_VALUE || str1.equals("") || str2.equals("")) {
                System.out.println(-1);
            } else {
                System.out.println(res);
            }
        }
    }
}

